package com.LC.快排;

// class QuickSort {
//    public static void quickSort(int[] arr,int low,int high){
//        int i,j,temp,t;
//        if(low>high){return;}
//        i=low;
//        j=high;
//        //temp就是基准位
//        temp = arr[low];
//        while (i<j) {
//            //先看右边，依次往左递减
//            while (temp<=arr[j]&&i<j) {j--;}
//            //再看左边，依次往右递增
//            while (temp>=arr[i]&&i<j) {i++;}
//            //如果满足条件则交换
//            if (i<j) {
//                t = arr[j];
//                arr[j] = arr[i];
//                arr[i] = t;}
//        }
//        //最后将基准为与i和j相等位置的数字交换
//        arr[low] = arr[i];//基准位置与i相等
//        arr[i] = temp;
//        //递归调用左半数组
//        quickSort(arr, low, j-1);
//        //递归调用右半数组
//        quickSort(arr, j+1, high);
//    }
//
//
//    public static void main(String[] args){
//        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
//        quickSort(arr, 0, arr.length-1);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.println(arr[i]);
//        }
//    }
//}
//什么是基准位？   基准位就是指，在这个数组中，基准位的数字是最小的，这个数字就是基准位。
//
class QuickSort {
    public void quickSort(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i=low;
        int j=high;
        int temp = arr[low];//基准位
        while(i<j){
            while(temp<=arr[j]&&i<j){j--;}  //先看右边，依次往左递减 直到找到比基准位小的
            while(temp>=arr[i]&&i<j){i++;}  //再看左边，依次往右递增 直到找到比基准位大的
            //如果满足条件则交换  经过上面的循环，i和j相等或者找到可以左右交换的两个数字
            if(i<j){//
                //交换
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
            //循环结束后，i和j相等，可以交换 将基准位置与i交换 且arr[i]
            //每一轮最后一个数一定要比基数小（为了跟右边的基数交换位置）
            //哨兵j 是为了找到比基数小的数字所以最后一步一定是比基准位置小的数**********************
            //现在low = j
//            int temp = arr[low];//基准位
            arr[low] = arr[i];   //最后将基准为与i和j相等位置的数字交换// https://blog.csdn.net/shujuelin/article/details/82423852
            arr[i] = temp;        //基准位置与i相等
            //递归调用左半数组
            quickSort(arr, low, j-1);
            //递归调用右半数组
            quickSort(arr, j+1, high);
        }
    }
    public static void main(String[] args) {
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        QuickSort qs = new QuickSort();
        qs.quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

//        方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。
//        刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。